#include <iostream>

using namespace std;

//看到“在有序范围内查找满足某条件的最大（或最小）值”，并且有单调性，第一反应就应该是二分查找！
class Solution 
{
public:
	int mySqrt(int x) 
	{
		if (x == 0 || x == 1) 
		{
			return x;
		}
		
		int left = 0;
		int right = x;
		int result = -1;		//标志位，代表默认无解
		
		while (left <= right) 
		{
			int mid = left + (right - left) / 2;
			
			if ((long long)mid * mid <= x)		//防止上溢
			{
				result = mid;    // 记录当前符合条件的结果
				left = mid + 1;  // 继续向右寻找更大的
			}
			else 
			{
				right = mid - 1; // mid太大了，缩小范围
			}
		}
		
		return result;
	}
};

int main() 
{
	Solution sol;
	int x;
	
	cout << "请输入一个非负整数 x: ";
	cin >> x;
	
	int result = sol.mySqrt(x);
	cout << "平方根的整数部分为: " << result << endl;
	
	return 0;
}

